#include <iostream>
#include <vector>
#include <unordered_map>
#include <cassert>

using namespace std;

// 169. 多数元素

// 使用hash表
// Time Complexity: O(n)
// Space Complexity: O(n)

class Solution {

public:
    int majorityElement(vector<int> &nums) {
        assert(nums.size() > 0);

        unordered_map<int, int> records;
        for(int num: nums)
            records[num]++;

        for(pair<int,int> record: records)
            if(record.second > nums.size() / 2)
                return record.first;

        throw invalid_argument("No Solution!");
    }
};